import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 三数之和 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        // -4 -1 -1 0 1 2
        for (int i = 0; i < n - 2;) {
            int cur = -nums[i];
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                if (nums[left] + nums[right] > cur) {
                    right--;
                } else if (nums[left] + nums[right] < cur) {
                    left++;
                } else {
                    ans.add(List.of(nums[left],nums[right],-cur));
                    // 去重
                    while (left < n && nums[left + 1] == nums[left]) {
                        left++;
                    }
                    left++;
                    while (right < n && nums[right - 1] == nums[right]) {
                        right--;
                    }
                    right--;
                }
            }
            // 去重
            while (i + 1 < n && nums[i + 1] == nums[i]) {
                i++;
            }
            i++;
        }
        return ans;
    }
}
